﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution62
{
    //记录到达每一个点的路线数
    //到达当前点有四个方向，上下左右，都加上
    //转移方程DP[i][j]=DP[i-1][j]+DP[i+1][j]+DP[i][j-1]+DP[i][j+1]

    //到达当前点有四个方向，上左，都加上
    //转移方程DP[i][j]=DP[i-1][j]+DP[i][j-1]
    public int UniquePaths(int m, int n)
    {
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i] = new int[n];
        }

        //初始状态，最上边只有一种可能，左边过来
        for (int i = 0;i < n; i++)
        {
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++)
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                Console.WriteLine("i:   "+ i+"  j:  "+j);
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
return dp[m - 1][n-1];

    }
}
class Program62
{
    static void Main62(string[] args)
    {
        int m = 3, n = 7;
        Solution62 solution = new Solution62();
     int res=   solution.UniquePaths(m, n);
        Console.WriteLine(res);
    }
}
